#include <stdio.h>
#include <stdlib.h>
#include "2.h"





void FastSort(int *a,int start,int end)
{
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        while(a[right]>temp&&left<right)
        {
            right--;
        }
        if(left<right)
        {
            a[left]=a[right];
            left++;
        }
        while(left<right&&a[left]<temp)
        {
            left++;
        }
        if(left<right)
        {
        a[right]=a[left];
        right--;
        }
        a[left]=temp;
        
        FastSort(a,start,left-1);
        FastSort(a,right+1,end);
    }
}

void FreeArray(Array *array)
{
    if(array->a != NULL)
    {
        free(array->a);
        array->a = NULL;
        array->len = 0;
    }
}

int Initialize(Array *array)
{
    array->a = (elememtype *)malloc(sizeof(elememtype) * array->size);
    if(array->a == NULL)
    {
        printf("malloc error!\n");
        return false;
    }
    return true;
}

int InsertArray(Array *array,elememtype element)
{
    if(array->len == array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return false;
        }
    }
    array->a[array->len] = element;
    array->len++;
    return true;
}

int ReallocArray(Array *array)
{
    elememtype *temp = array->a;
    array->size = array->size * 2;
    array->a = (elememtype *)malloc(sizeof(elememtype) * array->size);
    if(array->a== NULL)
    {
        printf("ReallocArray error!\n");
        array->a = temp;
        array->size = array->size / 2;
        return false;
    }

    for(int i = 0; i < array->len; i++)
    {
        array->a[i] = temp[i];
    }

    free(temp);
    temp=NULL;
    return true;

}

void Trave(Array *array)
{
    for(int i=0;i<array->len;i++)
    {
        printf("%d ",array->a[i]);
    }
    printf("\n");
}
void ReTrave(elememtype *a,int len)
{
    for(int i=len-1;i>=0;i--)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

int InsertTail(Array *array,elememtype data)
{
    if(array->len>=array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return false;
        }
    }
    array->a[array->len++]=data;
    return true;
}

int InsertHead(Array *array,elememtype data)
{
    if(array->len>=array->size)
    {
        
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return false;
        }
    }
    for(int i=array->len;i>0;i--)
    {
        array->a[i]=array->a[i-1];
    }
    array->a[0]=data;
    array->len++;
    return true;

}

void InsertIndex(Array *array,elememtype data,int index)
{
    if(array->len>=array->size)
    {
        printf("out of range\n");
        return ;
    }
    if(index<0||index>array->len)
    {
        printf("intvalid place\n");
        return;
    }
    for(int i=array->len;i>index;i--)
    {
        array->a[i]=array->a[i-1];
    }
    array->a[index]=data;
    array->len++;
}

int RemoveIndex(Array *array,int index)
{
    if(index<0||index>=array->len)
    {
        printf("error\n");
        return false;
    }

    for(int i=index;i<array->len-1;i++)
    {
        array->a[i]=array->a[i+1];
    }
    array->len--;
    return true;

}
void RemoveElement(Array *array,elememtype data)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==data)
        {
            RemoveIndex(array,i);
            i--;
        }
    }
}

elememtype FindIndex(Array *array,int index)
{
    if(index<0||index>=array->len)
    {
        printf("error\n");
        return false;
    }
    return array->a[index];
}

int *FindElement(Array *array,elememtype data)
{
    int *p=(int *)malloc(sizeof(int)*array->len+1);
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==data)
        {
            p[count++]=i;
        }
    }
    p[count]=-1;
    return p;
}
int SetvalueIndex(Array *array,int index,elememtype data)
{
    if(index<0||index>=array->len)
    {
        printf("error\n");
        return false;
    }

    array->a[index]=data;
    return true;
}

void  SetvaluElement(Array *array,elememtype data1,elememtype data2)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==data1)
        {
            array->a[i]=data2;
            
        }
    }
}

void FindIntersection(Array *array,Array *array1,Array *array2)
{
    for(int i=0;i<array->len;i++)
    {
        for(int j=0;j<array1->len;j++)
        {
            if(array->a[i]==array1->a[j])
            {
                int flag=0;
                for(int k=0;k<array2->len;k++)
                {
                    if(array2->a[k]==array1->a[j]&array->a[i]==array2->a[k])
                        flag=1;
                }
                if(flag==0)
                    array2->a[array2->len++]=array1->a[j];
            }
        }
    }
}

void Deduplication(Array *array)
{
    for(int i=0;i<array->len;i++)
    {
        for(int j=i+1;j<array->len;j++)
        {
            if(array->a[i]==array->a[j])
            {
                RemoveIndex(array,j);
                j--;
            }
        }
    }
}

void Deduplication2(Array *array)
{
    FastSort(array->a,0,array->len-1);
    for(int i=0;i<array->len-1;i++)
    {
        if(array->a[i+1]==array->a[i])
        {
            RemoveIndex(array,i+1);
            i--;
        }
    }
}

void FindUnionSet(Array *array,Array *array1,Array *array2)
{
    array2->len=array->len+array1->len;
    for(int i=0;i<array->len;i++)
    {
        array2->a[i]=array->a[i];
    }
    for(int i=array->len;i<array2->len;i++)
    {
        array2->a[i]=array1->a[i-array->len];
    }
    Deduplication2(array2);
}

void MergeArray(Array *array,Array *array1,Array *array2)
{
    array2->len=array->len+array1->len;
    for(int i=0;i<array->len;i++)
    {
        array2->a[i]=array->a[i];
    }
    for(int i=array->len;i<array2->len;i++)
    {
        array2->a[i]=array1->a[i-array->len];
    }
    FastSort(array2->a,0,array2->len-1);
}

